#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/21 16:16
# ===========================================
#       题目名称： 19. 删除链表的倒数第 N 个结点
#       题目地址： https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================
from utils import StringUtils


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    """
        实现思路 ：
            迭代吧
    """

    def removeNthFromEnd(self, head, n):
        temp_node = head
        # 1. 先获取链表的长度， 找到要干掉的倒数第几个的节点位置
        node_len = 1
        while temp_node.next:
            temp_node = temp_node.next
            node_len += 1
        # 2. 获取要删除的元素
        del_node_last_index = node_len - n  # 要删除元素的上一个位置
        # 3. 如果 del_node_last_index 为0 则表示第一个
        if del_node_last_index == 0:
            head = head.next
        else:
            temp_node = head  # 本身是一个元素
            while del_node_last_index > 1:
                temp_node = temp_node.next
                del_node_last_index -= 1
            del_node = temp_node.next
            if del_node:
                del_node_last = del_node.next
                temp_node.next = del_node_last
        return head

    def removeNthFromEnd2(self, head, n):
        """
            实现有误
        """
        temp_node = head
        # 1. 先获取链表的长度， 找到要干掉的倒数第几个的节点位置
        node_len = 1
        while temp_node.next:
            temp_node = temp_node.next
            node_len += 1
        del_node_index = node_len - n  # 0 - 3
        # 2. 根据位置再进行删除
        cur_index = 0
        temp_node = head
        if del_node_index - 1 >= 0:
            while cur_index < del_node_index - 1:
                temp_node = temp_node.next
                cur_index += 1
            del_node = temp_node.next
            if del_node:
                del_node_next_node = del_node.next
                temp_node.next = del_node_next_node
        else:
            head = None

        return head


if __name__ == '__main__':
    s = Solution()
    # [1,2,3,5]
    print(StringUtils.to_string(s.removeNthFromEnd(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), n=2)))
    # []
    print(StringUtils.to_string(s.removeNthFromEnd(head=ListNode(1), n=1)))
    # [1]
    print(StringUtils.to_string(s.removeNthFromEnd(head=ListNode(1, ListNode(2)), n=1)))
    # [2]
    print(StringUtils.to_string(s.removeNthFromEnd(head=ListNode(1, ListNode(2)), n=2)))
